#include<iostream>
using namespace std;
const int MAX_N = 1 << 17;
const int INF_MAX = 100000000;

// 存储线段树的全局数组
int n,dat[2*MAX_N-1];

// 初始化
void init(int n_){
    // 为了简单起见，把元素扩大到2的幂
    n = 1;
    while (n<n_) n*=2;

    // 把所有的值都设为INF_MAX
    for(int i=0;i<2*n-1;i++){
        dat[i] = INF_MAX;
    }
}

// 把第k个值（0-indexed）更新为a
void update(int k,int a){
    k += n-1; // 在存储中的下标
    dat[k] = a;
    while(k >0){
        int parent = (k-1)/2;
        if(dat[k] >= dat[parent])
            break;
        else{
            dat[parent] = dat[k];
        }
        k = parent;
    }
}

// 求[a,b)的最小值
// 后面的参数是为了计算起来方便而传进来的
// k是结点编号，l和r表示这个结点对应的区间是[l,r)
// 在外部调用时，用query(a,b,0,0,n)
int query(int a,int b,int k,int l,int r){
    if(r<=a || b<=l)
        return INT_MAX;
    if(a<=l && b>=r)
        return dat[k];

    int vl = query(a,b,k*2+1,l,(l+r)/2);
    int vr = query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
}